package leetcode100;

// TODO 中心扩散法 【-】 最长回文子串
// TODO https://leetcode.cn/problems/longest-palindromic-substring/solution/zui-chang-hui-wen-zi-chuan-by-leetcode-solution/

public class lc100_0005 {

    public String longestPalindrome(String s) {
        int n = s.length(), maxLen = 0;
        int tmpL = 0, tmpR = 0;

        for (int i = 0; i < n; i++) {
            int[] arr1 = expand(i, i, s);
            int[] arr2 = expand(i, i+1, s);

            int len1 = arr1[1] - arr1[0] + 1;
            int len2 = arr2[1] - arr2[0] + 1;

            if (len1 > maxLen) {
                maxLen = len1;
                tmpL = arr1[0];
                tmpR = arr1[1];
            }
            if (len2 > maxLen) {
                maxLen = len2;
                tmpL = arr2[0];
                tmpR = arr2[1];
            }
        }

        return s.substring(tmpL, tmpR+1);
    }

    public int[] expand(int left, int right, String s) {
        for (; left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right); left--, right++) {
        }
        return new int[]{left+1, right-1};
    }

}
